functor Types2 (S : TYPES_STRUCTS2) : TYPES2 =
struct
  open S
  
  structure Id = Id
  
  datatype t
    = Ns
    | Voidt
    | Intt
    | Boolt
    | Structt of {id : Id.t, offSet : Intl.t, ty : t} list * (unit ref)
    | Arrayt of Intl.t * t
    | Pointt of t
    | Name of Id.t
    | Product of t list
    | Funct of t * t
  
  fun equals (ty1, ty2) =
      case (ty1, ty2)
       of (Voidt, Voidt) => true
        | (Intt, Intt) => true
        | (Boolt, Boolt) => true
        | (Ns, Pointt _) => true
        | (Pointt _, Ns) => true
        | (Ns, Ns) => true
        | (Pointt t1, Pointt t2) => equals (t1, t2)
        | (Structt (_, u1), Structt (_, u2)) => u1 = u2          
        | (Arrayt (i1, t1), Arrayt (i2, t2)) => Intl.equals (i1, i2) andalso equals (t1, t2)
        | (Product l1, Product l2) =>
          let fun cook (lx, ly) =
                  case (lx, ly)
                   of ([], []) => true
                    | (x :: xs, y :: ys) =>
                      if equals (x, y)
                      then cook (xs, ys)
                      else false
                    | _ => false
          in  cook (l1, l2)
          end
        | (Name id1, Name id2) => Id.equals (id1, id2)
        | (Funct (t1, t2), Funct (t3, t4)) => equals (t1, t3) andalso equals (t2, t4)
        | _ => false
       
  fun isPtTy ty =
      case ty
       of Pointt _ => true
        | _ => false
  
  fun toString t =
      case t
       of Ns => "Ns"
        | Voidt => "void"
        | Intt => "int"
        | Boolt => "bool"
        | Structt (l, u) =>
          let fun cook lx =
                  case lx
                   of [] => []
                    | [{id, offSet, ty}] => [Id.toString id, ":", toString ty]
                    |  {id, offSet, ty} :: xs => ([Id.toString id, ":", toString ty] @ [", "]) @ (cook xs)
              val l1 = String.concat (cook l)
          in  String.concat ["struct{", l1, "}"]
          end
        | Arrayt (i, t) => String.concat [toString t, "[", Intl.toString i, "]"]
        | Pointt t => String.concat [toString t, "*"]
        | Name id => Id.toString id
        | Product l =>
          let val l1 = List.map toString l
              val l2 = 
                  let fun cook aim =
                      case aim
                        of [] => []
                         | [x] => [x]
                         | x :: xs => (x :: [", "]) @ (cook xs)
                  in  cook l1
                  end
              val l3 = String.concat l2
          in  String.concat ["[",  l3, "]"]
          end
        | Funct (t1, t2) => String.concat [toString t1, "->", toString t2]
        
  fun size t =
      case t
       of Ns => 1
        | Voidt => 1
        | Intt => 1
        | Boolt => 1
        | Structt (l, u) => List.length l
        | Arrayt (i, t) => Intl.toInt i
        | Pointt t => 1
        | Name id => raise Fail "compiler bug"
        | Product l => List.length l
        | Funct (t1, t2) => raise Fail "compiler bug"
end
